package org.example.array;

/**
 * 数组二分查找
 * @author: guochao.bj@fang.com
 * @createDate: 2022/5/16 09:09
 */
public class practiceArray02 {


    /**
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     *
     * 输入: nums = [-1,0,3,5,9,12], target = 9
     * 输出: 4
     *
     * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md
     * 分析：有序数组，无重复数据,可以考虑是否使用数组
     *
     * 是因为left + right 在某种情况下可能会超过基本类型所能容纳的最大值,而且 >> (位运算) 比 / 运算要快一点
     *
     */

    public static void main(String[] args) {
        int[] nums ={-1,0,3,5,9,12};

        System.out.println(getTargetIndex(nums,9));

    }



    private static int getTargetIndex(int[] nums,int target){

        if (target<nums[0]||target>nums[nums.length-1]){
            return -1;
        }

        int left=0;
        int right=nums.length-1;

        while (left<=right){
            //int minddle=left+((right-left)/2);
            //右移运算符>>,运算结果正好能对应一个整数的二分之一值，这就正好能代替数学上的除2运算，但是比除2运算要快。
            int minddle=left+((right-left)>>1);
            if (nums[minddle]==target){
                // 数组中找到目标值，直接返回下标
                return minddle;
            }else {
                if (nums[minddle]>target){
                    // target 在左区间，所以[left, middle - 1]
                    right=minddle-1;
                }else {
                    // target 在右区间，所以[middle + 1, right]
                    left=minddle+1;
                }
            }
        }
        return -1;
    }



}
